﻿
namespace Homework21
{
    /// <summary>
    /// 运筹学，最短路问题
    /// </summary>
    public class ShortestPathFinder
    {
        // 邻接矩阵
        private int[,] adjacencyMatrix;

        // 存储从起点到每个节点的最短距离
        private int[] distances;

        // 记录哪些节点已经被访问过
        private bool[] visited; 

        public ShortestPathFinder(int[,] matrix)
        {
            adjacencyMatrix = matrix;

            // 获取节点数量
            int n = matrix.GetLength(0); 
            distances = new int[n];
            visited = new bool[n];
        }

        public void FindShortestPaths(int startNode)
        {
            // 获取节点数量
            int n = adjacencyMatrix.GetLength(0); 

            // 初始化距离数组，所有距离初始化为最大整数值
            for (int i = 0; i < n; i++)
            {
                distances[i] = int.MaxValue;
                visited[i] = false;
            }

            // 起始节点到自身的距离为0
            distances[startNode - 1] = 0;

            // 对于每个节点，更新其最短路径
            for (int count = 0; count < n - 1; count++)
            {
                // 获取当前未被访问过的节点中，距离最小的那个节点
                int u = MinDistance(n);
                // 标记该节点已被访问
                visited[u] = true;

                // 更新与已选节点相连的节点的距离
                for (int v = 0; v < n; v++)
                {
                    // 如果目标节点未被访问过，且通过当前节点到达目标节点的路径比已知的更短，则更新距离
                    if (!visited[v] && adjacencyMatrix[u, v] != 0 && distances[u] != int.MaxValue && distances[u] + adjacencyMatrix[u, v] < distances[v])
                    {
                        distances[v] = distances[u] + adjacencyMatrix[u, v];
                    }
                }
            }
        }

        // 找到当前未被访问过的节点中，距离最小的节点索引
        private int MinDistance(int n)
        {
            int min = int.MaxValue, min_index = -1;

            // 遍历所有节点，寻找最小距离
            for (int v = 0; v < n; v++)
            {
                if (!visited[v] && distances[v] <= min)
                {
                    min = distances[v];
                    min_index = v;
                }
            }

            return min_index;
        }

        // 获取最短距离数组
        public int[] GetDistances()
        {
            return distances;
        }

        public static void Main(string[] args)
        {
            // 定义邻接矩阵，0表示两个节点之间没有直接连接
            int[,] adjacencyMatrix = {
            {0, 250, 400, 0, 0, 0},
            {0, 0, 100, 300, 0, 0},
            {0, 0, 0, 150, 275, 0},
            {0, 0, 0, 0, 100, 200},
            {0, 0, 0, 0, 0, 150},
            {0, 0, 0, 0, 0, 0}
        };

            // 创建一个最短路径查找器对象
            ShortestPathFinder finder = new ShortestPathFinder(adjacencyMatrix);

            // 计算从节点1出发到其他所有节点的最短路径
            finder.FindShortestPaths(1);

            // 获取并输出最短路径结果
            int[] distances = finder.GetDistances();
            Console.WriteLine("Shortest paths from node 1:");
            for (int i = 0; i < 6; i++)
            {
                // 注意：由于节点编号是从1开始的，而数组索引是从0开始的，因此这里需要做相应的转换
                Console.WriteLine($"To node {i + 1}: {distances[i]}");
            }
        }
    }
}
